package com.buddy.leetcode._02;

/**
 * 给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
 * 你可以假设除了数字 0 之外，这两个数字都不会以零开头。
 *
 * 示例：
 * 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
 * 输出：7 -> 0 -> 8
 * 原因：342 + 465 = 807
 */
public class AddTwoNumbers {
    private static int temp = 0;

    /**
     * 时间复杂度：O(max(m,n))
     * 假设 mmm 和 nnn 分别表示 l1l1l1 和 l2l2l2 的长度，
     * 上面的算法最多重复 max(m,n)\次。
     * 空间复杂度：O(max(m,n))
     * 新列表的长度最多为 max(m,n)+1。
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers(ListNode l1,ListNode l2){
        ListNode resultNode = new ListNode(-1);
        ListNode cur = resultNode;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int d1 = l1 == null ? 0 : l1.val;
            int d2 = l2 == null ? 0 : l2.val;
            int sum = d1 + d2 + carry;
            carry = sum >= 10 ? 1 : 0;
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        if (carry == 1) cur.next = new ListNode(1);
        return resultNode.next;
    }



    public ListNode myAddTwoNumbers(ListNode l1, ListNode l2) {
        int v1=0,v2=0,sum=0;
        ListNode next2=null,next1 = null;
        if(l1 != null ){
            v1 = l1.val;
            next1 = l1.next;
        }
        if(l2 != null){
            v2 = l2.val;
            next2 = l2.next;
        }
        sum = v1+v2;
        int sumVal = sum % 10;
        temp = sum/10;
        ListNode resultListNode = new ListNode(sumVal);
        if (next1 != null || next2 != null){
            if(next1 != null){
                next1.val = next1.val+temp;

            }else if(next2!= null){

                next2.val = next2.val+temp;
            }
            resultListNode.next = addTwoNumbers(next1,next2);
            temp = 0;
        }else if(0!= temp){
            resultListNode.next = new ListNode(temp);
        }
        return resultListNode;
    }

}
